package algorithm.niuke;

import java.util.LinkedList;

public class B可能的二分法 {
    /*
     * 给定一组 N 人（编号为 1, 2, ..., N）， 我们想把每个人分进任意大小的两组。
     * 
     * 每个人都可能不喜欢其他人，那么他们不应该属于同一组。
     * 
     * 形式上，如果 dislikes[i] = [a, b]，表示不允许将编号为 a 和 b 的人归入同一组。
     * 
     * 当可以用这种方法将每个人分进两组时，返回 true；否则返回 false。
     * 
     * 
     * 
     * 示例 1：
     * 
     * 输入：N = 4, dislikes = [[1,2],[1,3],[2,4]] 输出：true 解释：group1 [1,4], group2
     * [2,3] 示例 2：
     * 
     * 输入：N = 3, dislikes = [[1,2],[1,3],[2,3]] 输出：false 示例 3：
     * 
     * 输入：N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]] 输出：false
     * 
     * 
     * 提示：
     * 
     * 1 <= N <= 2000 0 <= dislikes.length <= 10000 1 <= dislikes[i][j] <= N
     * dislikes[i][0] < dislikes[i][1] 对于 dislikes[i] == dislikes[j] 不存在 i != j
     */
    public boolean possibleBipartition(int N, int[][] dislikes) {
        int[] map = new int[N + 5];
        for (int[] dislike : dislikes) {
            int a = dislike[0];
            int b = dislike[1];
            int ag = map[a];
            int bg = map[b];
            if (ag != 0 && bg != 0) {
                if (ag == bg) {
                    return false;
                } else {
                    transfer(map, Math.min(ag, -b), Math.max(ag, -b));
                    transfer(map, Math.min(bg, -a), Math.max(bg, -a));
                }
                continue;
            }
            if (ag != 0 && bg == 0) {
                map[b] = map[-ag];
                continue;
            }
            if (ag == 0 && bg != 0) {
                map[a] = map[-bg];
                continue;
            }
            if (ag == 0 && bg == 0) {
                map[a] = -b;
                map[b] = -a;
            }
        }
        return true;
    }

    void transfer(int[] map, int g1, int g2) {
        if (g1 == g2) {
            return;
        }
        int len = map.length;
        for (int i = 0; i < len; i++) {
            if (map[i] == g1) {
                map[i] = g2;
            }
        }
    }

    public static void main(String[] args) {
        B可能的二分法 run = new B可能的二分法();
        int N = 3;
        int[][] dislikes = { { 1, 4 }, { 2, 3 }, { 3, 4 } };
        run.possibleBipartition(N, dislikes);
    }
}
